// The Single Source Shortest Path (SSSP) problem
// can be solved efficiently on a DAG in O(V+E
// time. This is due to the fact that the nodes can be ordered 
// in a topological ordering via topsort and processed sqquentially
// https://www.bilibili.com/video/BV11E411o7Fb?p=7
#include <bits/stdc++.h>
using namespace std;

template <typename T>
vector<T> reverseVector(vector<T> &vec){
    int i = 0;
    int j = vec.size()-1;
    while(i < j){
        swap(vec[i],vec[j]);
        i++;
        j--;
    }
    return vec;
}

template <typename T>
void printVector(vector<T> nums)
{
    for (auto n : nums)
    {
        cout << n << ' ';
    }
    cout<<endl;
}

void dfs(int node, vector<bool>& V,vector<int>& visitedNodes, vector<vector<int>> &graph){
    V[node] = true;
    vector<int> edges = graph[node];
    for(int to : edges){
        if(V[to] == false){
            dfs(to,V,visitedNodes,graph);
        }
    }
    visitedNodes.push_back(node);
    return;
}


// Assumption: graph is stored as adjacency list
vector<int> topologicalSort(vector<vector<int>> graph){
    int N = graph.size(); // number of nodes
    vector<bool> V(N);
    vector<int> ordering;

    for(int i = 0; i < N; i++){
        if(V[i] == false){
            vector<int> visitedNodes;
            dfs(i,V,visitedNodes,graph);
            for(auto nodeID : visitedNodes){
                ordering.push_back(nodeID);
            }
        }
    }
    return reverseVector(ordering);
}

// graph - adjacency list
// val - edges' weights of index node
// startNode - start node 
vector<int> dagShortestPath(vector<vector<int>> graph, vector<vector<int>> val, int startNode){
    int numNodes = graph.size();
    vector<int> topsort = topologicalSort(graph);
    vector<int> dist(numNodes,-1);
    dist[startNode] = 0;
    for(int i = 0; i < numNodes; i++){
        int nodeIndex = topsort[i];
        if(dist[nodeIndex] != -1){
            vector<int> neighbours = graph[nodeIndex];
            vector<int> weights = val[nodeIndex];

            for(int i = 0; i < neighbours.size(); i++){
                int neighbour = neighbours[i];
                int newDist = dist[nodeIndex] + weights[i];
                if(dist[neighbour]==-1) dist[neighbour] = newDist;
                else dist[neighbour] = min(dist[neighbour],newDist);
            }

        }
    }
    return dist;
}

int main(){
    vector<vector<int>> graph = {
        {'B','C'},
        {'C','D','E'},
        {'D','G'},
        {'E','F','G'},
        {'H'},
        {'H'},
        {'H'},
        {}
    };
    vector<vector<int>> val = {
        {3,6},
        {4,4,11},
        {8,11},
        {-4,5,2},
        {9},
        {1},
        {2},
        {}
    };
    for(auto &a:graph){
        for(auto &b : a){
            b = b - 'A';
        }
    }
    printVector(dagShortestPath(graph,val,0));
    return 0;
}